﻿int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) 
{

	int* ans = malloc(numsSize * sizeof(int));
	int i = 0;
	for (i = 0; i < numsSize; i++) {
		int j = 0;
		int count = 0;
		for (j = 0; j < numsSize; j++) {
			if (nums[j] < nums[i]) {
				count++;
			}
		}
		ans[i] = count;
	}
	*returnSize = numsSize;
	return ans;
}	

//解法⼆（排序，⼆分查找）

int low(int* order, int orderSize, int u) {
	int i;
	int l = 0, r = orderSize - 1;
	while (l < r) {
		int mid = (l + r) / 2;

		if (order[mid] < u) l = mid + 1;
		else r = mid;
	}
	return l;
}
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {
	int* ans = malloc(numsSize * sizeof(int));
	int* order = malloc(numsSize * sizeof(int));
	int i = 0, j = 0;
	for (i = 0; i < numsSize; i++) order[i] = nums[i];	
	for (i = 0; i < numsSize; i++) {
		for (j = 0; j < numsSize - i - 1; j++) {
			if (order[j] > order[j + 1]) {
				int u = order[j];
				order[j] = order[j + 1];
				order[j + 1] = u;
			}
		}
	}
	for (int i = 0; i < numsSize; i++) {
		ans[i] = low(order, numsSize, nums[i]);
	}
	*returnSize = numsSize;
	return ans;
}